package com.husk.leetcode.basic;

import java.util.*;
import java.util.stream.Collectors;

/**
 * <p>
 *
 * </p>
 *
 * @author hushunke@sm.vvip-u.com
 * @since 2021/3/18
 */
public class Solution {

    // 带缓存的递归算法
    private Map<Integer, Integer> cache = new HashMap<>();

    /**
     * #888 公平的糖果棒交换
     * <p>
     * https://leetcode-cn.com/problems/fair-candy-swap/
     *
     * @param A
     * @param B
     * @return
     */
    public int[] fairCandySwap(int[] A, int[] B) {
        int sumA = Arrays.stream(A).sum();
        int sumB = Arrays.stream(B).sum();

        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < B.length; j++) {
                if (sumA - A[i] + B[j] == sumB + A[i] - B[j]) {
                    return new int[]{A[i], B[j]};
                }
            }
        }
        return null;
    }

    /**
     * #698. 划分为k个相等的子集
     * [0,1,2,3,4,5]
     * <p>
     * https://leetcode-cn.com/problems/partition-to-k-equal-sum-subsets/
     *
     * @param nums
     * @param k
     * @return
     */
    public boolean canPartitionKSubsets(int[] nums, int k) {
        if (nums.length < k || k == 0) {
            return false;
        }

        int sum = Arrays.stream(nums).sum();
        int avg = sum / k;

        if (avg * k != sum) {
            // 除不尽的情况
            return false;
        }
        Arrays.sort(nums);
        // 从nums中取任意个值，求和等于item

        int maxIndex = nums.length - 1;

        if (nums[maxIndex] > avg) {
            // 最大的值大于平均值，不可能满足条件
            return false;
        }
        while (maxIndex > 0 && nums[maxIndex] == avg) {
            // 去掉排序后，尾部等于平均数的
            maxIndex--;
            k--;
        }
        return search(new int[k], maxIndex, nums, avg);
    }

    private boolean search(int[] group, int maxIndex, int[] nums, int avg) {
        if (maxIndex < 0) {
            return true;
        }
        //
        int v = nums[maxIndex--];

        for (int i = 0; i < group.length; i++) {
            if (group[i] + v <= avg) {
                group[i] += v;
                if (this.search(group, maxIndex, nums, avg)) {
                    return true;
                }
                group[i] -= v;
            }
            if (group[i] == 0) {
                break;
            }
        }
        return false;
    }

    /**
     * #4.给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
     * <p>
     * https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {

        int[] array = new int[nums1.length + nums2.length];

        for (int i = 0, j = 0, index = 0; ; index++) {
            if (i == nums1.length && j == nums2.length) {
                break;
            } else if (i == nums1.length) {
                array[index] = nums2[j];
                j++;
                continue;
            } else if (j == nums2.length) {
                array[index] = nums1[i];
                i++;
                continue;
            }

            if (nums1[i] >= nums2[j]) {
                array[index] = nums2[j];
                j++;
            } else if (nums1[i] < nums2[j]) {
                array[index] = nums1[i];
                i++;
            }
        }

        int count = array.length;

        if (count % 2 == 0) {
            return (array[count / 2 - 1] + array[count / 2]) / 2d;
        } else {
            return array[count / 2];
        }
    }

    /**
     * #811 子域名访问计数
     * <p>
     * https://leetcode-cn.com/problems/subdomain-visit-count/
     *
     * @param cpdomains
     * @return
     */
    public List<String> subdomainVisits(String[] cpdomains) {
        Map<String, Integer> data = new HashMap<>();
        for (String item : cpdomains) {
            Integer count = Integer.valueOf(item.substring(0, item.indexOf(' ')));


            String site = item.substring(item.indexOf(" ") + 1);

            while (site.contains(".")) {
                data.merge(site, count, Integer::sum);
                site = site.substring(site.indexOf('.') + 1);
            }
            // 处理最后的尾巴
            data.merge(site, count, Integer::sum);
        }
        return data.keySet().parallelStream().map(key -> data.get(key) + " " + key).collect(Collectors.toList());
    }

    /**
     * 给定一组非负整数 nums，重新排列它们每个数字的顺序（每个数字不可拆分）使之组成一个最大的整数。
     * <p>
     * https://leetcode-cn.com/problems/largest-number/
     *
     * @param nums
     * @return
     */
    public String largestNumber(int[] nums) {
        String[] array = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            array[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(array, new LargestNumberComparator());
        if (array[0].equals("0")) {
            return "0";
        } else {
            return String.join("", array);
        }
    }

    private static class LargestNumberComparator implements Comparator<String> {
        @Override
        public int compare(String o1, String o2) {
            return -(o1 + o2).compareTo(o2 + o1);
        }
    }


    /**
     * 1423. 可获得的最大点数
     * <p>
     * https://leetcode-cn.com/problems/maximum-points-you-can-obtain-from-cards/
     *
     * @param cardPoints
     * @param k
     * @return
     */
    public int maxScore1(int[] cardPoints, int k) {
        int n = cardPoints.length;
        int windowSize = n - k;

        int sum = 0;
        for (int i = 0; i < windowSize; i++) {
            sum += cardPoints[i];
        }

        int minSum = sum;
        for (int i = windowSize; i < n; i++) {
            sum = sum + cardPoints[i] - cardPoints[i - windowSize];
            minSum = Math.min(sum, minSum);
        }
        return Arrays.stream(cardPoints).sum() - minSum;
    }

    /**
     * 1423. 可获得的最大点数
     * <p>
     * https://leetcode-cn.com/problems/maximum-points-you-can-obtain-from-cards/
     *
     * @param cardPoints
     * @param k
     * @return
     */
    public int maxScore(int[] cardPoints, int k) {
        int max = 0;
        for (int i = 0; i <= k; i++) {
            int sum = 0;
            for (int j = k - i - 1; j >= 0; j--) {
                sum += cardPoints[j];
            }
            for (int j = cardPoints.length - 1; j >= cardPoints.length - i; j--) {
                sum += cardPoints[j];
            }
            max = Math.max(max, sum);
        }
        return max;
    }


    /**
     * 821. 字符的最短距离
     * <p>
     * https://leetcode-cn.com/problems/shortest-distance-to-a-character/
     *
     * @param s
     * @param c
     * @return
     */
    public int[] shortestToChar(String s, char c) {
        int[] result = new int[s.length()];

        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == c) {
                list.add(i);
            }
        }
        for (int i = 0, j = 0; i < s.length(); i++) {
            int s1 = Math.abs(i - list.get(Math.max(j - 1, 0)));
            int s2 = Math.abs(list.get(Math.min(j, list.size() - 1)) - i);
            result[i] = Math.min(s1, s2);
            if (s.charAt(i) == c) {
                j++;
            }
        }
        return result;
    }

    /**
     * 面试题 16.16. 部分排序
     * <p>
     * https://leetcode-cn.com/problems/sub-sort-lcci/
     *
     * @param array
     * @return
     */
    public int[] subSort(int[] array) {
        if (array == null || array.length == 0 || array.length == 1) {
            return new int[]{-1, -1};
        }
        int maxIndex = 0, minIndex = array.length - 1;
        int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;

        for (int i = 0; i < array.length; i++) {
            if (array[i] >= max) {
                max = array[i];
            } else {
                maxIndex = i;
            }
        }
        for (int j = array.length - 1; j >= 0; j--) {
            if (array[j] <= min) {
                min = array[j];
            } else {
                minIndex = j;
            }
        }
        return minIndex < maxIndex ? new int[]{minIndex, maxIndex} : new int[]{-1, -1};
    }

    /**
     * 1773. 统计匹配检索规则的物品数量
     * items[i] = [typei, colori, namei]
     * <p>
     * https://leetcode-cn.com/problems/count-items-matching-a-rule/
     *
     * @param items
     * @param ruleKey
     * @param ruleValue
     * @return
     */
    public int countMatches(List<List<String>> items, String ruleKey, String ruleValue) {
        int count = 0;
        for (int i = 0; i < items.size(); i++) {
            List<String> list = items.get(i);
            if ("type".equals(ruleKey) && list.get(0).equals(ruleValue)) {
                count++;
            } else if ("color".equals(ruleKey) && list.get(1).equals(ruleValue)) {
                count++;
            } else if ("name".equals(ruleKey) && list.get(2).equals(ruleValue)) {
                count++;
            }
        }
        return count;
    }

    /**
     * 957. N 天后的牢房
     * <p>
     * 如果一间牢房的两个相邻的房间都被占用或都是空的，那么该牢房就会被占用。
     * 否则，它就会被空置。
     * <p>
     * https://leetcode-cn.com/problems/prison-cells-after-n-days/
     *
     * @param cells
     * @param n
     * @return
     */
    public int[] prisonAfterNDays(int[] cells, int n) {
        n = (n - 1) % 14 + 1; // TODO 如何用记忆法找出这个14循环

        for (int count = 0; count < n; count++) {
            int[] newCells = new int[cells.length];
            for (int i = 0; i < cells.length; i++) {
                // 第一个和最后一个一定为0
                if (i == 0) {
                    newCells[i] = 0;
                } else if (i == newCells.length - 1) {
                    newCells[i] = 0;
                } else {
                    newCells[i] = cells[i - 1] == cells[i + 1] ? 1 : 0;
                }
            }
            cells = newCells;
        }
        return cells;
    }

    /**
     * 216. 组合总和 III
     * 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
     * <p>
     * https://leetcode-cn.com/problems/combination-sum-iii/
     *
     * @param k
     * @param n
     * @return
     */
    public List<List<Integer>> combinationSum3(int k, int n) {
        // TODO
        return null;
    }


    /**
     * 70. 爬楼梯
     * <p>
     * https://leetcode-cn.com/problems/climbing-stairs/
     *
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        return this.climbStairsRecursion(n);
    }

    private int climbStairsRecursion(int n) {
        Integer data = cache.get(n);
        if (data != null) {
            return data;
        } else if (n <= 0) {
            cache.put(n, 0);
            return 0;
        } else if (n == 1 || n == 2) {
            cache.put(n, n);
            return n;
        }
        int result = this.climbStairsRecursion(n - 1) + this.climbStairsRecursion(n - 2);
        cache.put(n, result);
        return result;
    }

    public int rob2(int[] nums) {
        return this.robRecursion(nums, nums.length);
    }

    public int robRecursion(int nums[], int n) {
        Integer data = cache.get(n);
        if (data != null) {
            return data;
        }
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return nums[0];
        }
        int sum = Math.max(this.robRecursion(nums, n - 1), this.robRecursion(nums, n - 2) + nums[n - 1]);
        cache.put(n, sum);
        return sum;
    }


    /**
     * 1700. 无法吃午餐的学生数量
     * <p>
     * https://leetcode-cn.com/problems/number-of-students-unable-to-eat-lunch/
     *
     * @param students
     * @param sandwiches
     * @return
     */
    public int countStudents(int[] students, int[] sandwiches) {
        if (students == null || students.length == 0) {
            return 0;
        }
        if (sandwiches == null || sandwiches.length == 0) {
            return students.length;
        }
        Queue<Integer> queue = new LinkedList<>();
        Arrays.stream(students).forEach(queue::offer);
        for (int i = 0; i < sandwiches.length; i++) {
            if (queue.isEmpty()) {
                return 0;
            }
        }
        return 0;
    }

    /**
     * 78. 子集
     * <p>
     * https://leetcode-cn.com/problems/subsets/
     *
     * @param nums 不重复
     * @return
     */
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>()); // 空集
        for (int num : nums) {
            List<List<Integer>> temp = new ArrayList<>(); // 这个一字母的所有集合
            for (List<Integer> subset : result) {
                // 之前的所有集合加这个字母
                List<Integer> newSubset = new ArrayList<>(subset);
                newSubset.add(num);

                temp.add(newSubset);
            }
            result.addAll(temp);
        }
        return result;
    }


    /**
     * 90. 子集 II
     * <p>
     * https://leetcode-cn.com/problems/subsets-ii/
     *
     * @param nums 有重复元素
     * @return 所有子集，需要去重
     */
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        Set<List<Integer>> result = new HashSet<>();
        result.add(new ArrayList<>()); // 空集
        for (int num : nums) {
            Set<List<Integer>> temp = new HashSet<>(); // 这个一字母的所有集合
            for (List<Integer> subset : result) {
                // 之前的所有集合加这个字母
                List<Integer> newSubset = new ArrayList<>(subset);
                newSubset.add(num);

                temp.add(newSubset);
            }
            result.addAll(temp);
        }
        return new ArrayList<>(result);
    }

    /**
     * 5. 最长回文子串
     * https://leetcode-cn.com/problems/longest-palindromic-substring/
     * <p>
     *
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }
        int maxLen = 1;
        int begin = 0;
        char[] charArray = s.toCharArray();
        for (int i = 0; i < len - 1; i++) {
            for (int j = i + 1; j < len; j++) {
                if (j - i + 1 > maxLen && this.isPalindromic(charArray, i, j)) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }

    public boolean isPalindromic(char[] str, int left, int right) {
        while (left < right) {
            if (str[left] != str[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    /**
     * 1006. 笨阶乘
     * <p>
     * https://leetcode-cn.com/problems/clumsy-factorial/
     * <p>
     * × ÷ ＋ －
     *
     * @param N
     * @return
     */
    public int clumsy(int N) {
        Stack<Integer> stack = new Stack<>();
        stack.push(N);

        int n = N;
        int i = 0;
        while (true) {
            n--;
            if (n == 0) {
                break;
            }

            if (i % 4 == 0) {
                stack.push(stack.pop() * n);
            } else if (i % 4 == 1) {
                stack.push(stack.pop() / n);
            } else if (i % 4 == 2) {
                stack.push(n);
            } else if (i % 4 == 3) {
                stack.push(-n);
            }
            i++;
        }
        return stack.stream().mapToInt(Integer::valueOf).sum();
    }

    /**
     * 15. 三数之和
     * <p>
     * https://leetcode-cn.com/problems/3sum/
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        for (int first = 0; first < n; first++) {
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            int third = n - 1;
            int target = -nums[first];// b+c = -a
            for (int second = first + 1; second < n; second++) {
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                while (second < third && nums[second] + nums[third] > target) {
                    third--;
                }
                if (second == third) {
                    break;
                }
                if (nums[first] + nums[second] + nums[third] == 0) {
                    result.add(Arrays.asList(nums[first], nums[second], nums[third]));
                }
            }
        }
        return result;
    }

    public int reverse(int x) {
        if (x == 0) {
            return 0;
        }
        char[] chars = String.valueOf(x).toCharArray();
        for (int i = x < 0 ? 1 : 0, j = chars.length - 1; i < j; i++, j--) {
            char temp = chars[i];
            chars[i] = chars[j];
            chars[j] = temp;
        }
        int start = x < 0 ? 1 : 0;
        StringBuilder sb = new StringBuilder();
        for (int i = start; i < chars.length; i++) {
            sb.append(chars[i]);
        }
        try {
            Integer result = new Integer(sb.toString());
            return x < 0 ? -result : result;
        } catch (Exception e) {
            return 0;
        }
    }

    public int reverse2(int x) {
        int rev = 0;
        while (x != 0) {
            int pop = x % 10;
            x /= 10;
            if (rev > Integer.MAX_VALUE / 10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) {
                return 0;
            }
            if (rev < Integer.MIN_VALUE / 10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) {
                return 0;
            }
            rev = rev * 10 + pop;
        }
        return rev;
    }

    /**
     * 19. 删除链表的倒数第 N 个结点
     * <p>
     * 先前移n个，然后一起移动到末尾，滑动窗口
     * <p>
     * https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
     *
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode pre = new ListNode(0, head);
        ListNode start = pre, end = pre;
        while (n != 0) {
            start = start.next;
            n--;
        }
        while (start.next != null) {
            start = start.next;
            end = end.next;
        }
        end.next = end.next.next;
        return head;
    }

    /**
     * 17. 电话号码的字母组合
     * <p>
     * https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
     *
     * @param digits
     * @return
     */
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits == null || "".equals(digits)) {
            return result;
        }
        Map<Character, String> phoneMap = new HashMap<Character, String>() {
            {
                put('2', "abc");
                put('3', "def");
                put('4', "ghi");
                put('5', "jkl");
                put('6', "mno");
                put('7', "pqrs");
                put('8', "tuv");
                put('9', "wxyz");
            }
        };
        for (int i = 0; i < digits.length(); i++) {
            String cur = phoneMap.get(digits.charAt(i));
            List<String> temp = new ArrayList<>();
            for (int j = 0; j < cur.length(); j++) {
                char c = cur.charAt(j);
                if (result.size() == 0) {
                    temp.add(Character.toString(c));
                } else {
                    for (String s : result) {
                        temp.add(s + c);
                    }
                }
            }
            result = temp;
        }
        return result;
    }


    /**
     * 28. 实现 strStr()
     * <p>
     * 字符串匹配KMP算法
     * <p>
     * https://leetcode-cn.com/problems/implement-strstr/
     */
    public int strStr(String haystack, String needle) {
        if ("".equals(needle)) {
            return 0;
        }
        int n = haystack.length();
        int m = needle.length();
        for (int i = 0; i + m <= n; i++) {
            boolean flag = true;
            for (int j = 0; j < m; j++) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 剑指 Offer 52. 两个链表的第一个公共节点
     * https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode tempA = headA;
        ListNode tempB = headB;
        while (tempA != tempB) {
            tempA = tempA == null ? headB : tempA.next;
            tempB = tempB == null ? headA : tempB.next;
        }
        return tempA;
    }

    /**
     * 1418. 点菜展示表
     * <p>
     * https://leetcode-cn.com/problems/display-table-of-food-orders-in-a-restaurant/
     *
     * @param orders
     * @return
     */
    public List<List<String>> displayTable(List<List<String>> orders) {
        Set<String> foodItemSet = new HashSet<>();
        // table
        Map<Integer, TreeMap<String, Integer>> resultMap = new TreeMap<>();

        for (int i = 0; i < orders.size(); i++) {
            List<String> list = orders.get(i);
            Integer table = Integer.valueOf(list.get(1));// 桌号
            String foodItem = list.get(2); // 餐品名称
            foodItemSet.add(foodItem);

            // foodItem, count
            TreeMap<String, Integer> food = resultMap.get(table);
            if (food == null) {
                food = new TreeMap<>();
                resultMap.put(table, food);
            }
            Integer count = food.get(foodItem);
            if (count == null) {
                food.put(foodItem, 1);
            } else {
                food.put(foodItem, count + 1);
            }
        }
        LinkedList<String> foodItemList = new LinkedList<>(foodItemSet);
        Collections.sort(foodItemList);

        LinkedList<List<String>> result = new LinkedList<>();
        resultMap.entrySet().forEach(foodItem -> {
            List<String> item = new ArrayList<>();
            // 桌号
            Integer table = foodItem.getKey();
            // 每桌的菜
            TreeMap<String, Integer> food = foodItem.getValue();

            item.add(table.toString());
            for (int i = 0; i < foodItemList.size(); i++) {
                Integer count = food.get(foodItemList.get(i));
                item.add(count == null ? "0" : count.toString());
            }
            result.add(item);
        });

        foodItemList.addFirst("Table");
        result.addFirst(foodItemList);

        return result;
    }

    /**
     * 844. 比较含退格的字符串
     * <p>
     * https://leetcode-cn.com/problems/backspace-string-compare/
     *
     * @param s
     * @param t
     * @return
     */
    public boolean backspaceCompare(String s, String t) {
        return this.build(s).equals(this.build(t));
    }

    public String build(String s) {
        StringBuilder sb = new StringBuilder();
        int length = s.length();
        for (int i = 0; i < length; i++) {
            char ch = s.charAt(i);
            if (ch != '#') {
                sb.append(ch);
            } else {
                if (sb.length() > 0) {
                    sb.deleteCharAt(sb.length() - 1);
                }
            }
        }
        return sb.toString();
    }

    /**
     * 930. 和相同的二元子数组
     * <p>
     * https://leetcode-cn.com/problems/binary-subarrays-with-sum/
     *
     * @param nums
     * @param goal
     * @return
     */
    public int numSubarraysWithSum(int[] nums, int goal) {
        for (int i = 0; i < nums.length; i++) {
            System.out.println(nums[i]);
        }
        return 0;
    }


    /**
     * 274. H 指数
     * https://leetcode-cn.com/problems/h-index/
     *
     * @param citations
     * @return
     */
    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int h = 0, i = citations.length - 1;
        while (i >= 0 && citations[i] > h) {
            i--;
            h++;
        }
        return h;
    }


    /**
     * 275. H 指数 II
     * https://leetcode-cn.com/problems/h-index-ii/
     *
     * @param citations
     * @return
     */
    public int hIndex2(int[] citations) {
        int n = citations.length, left = 0, right = n - 1;
        while (left <= right) {
            int mid = left + (left + right) / 2;
            if (citations[mid] >= n - mid) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return n - left;
    }


    /**
     * 1846. 减小和重新排列数组后的最大元素
     * https://leetcode-cn.com/problems/maximum-element-after-decreasing-and-rearranging/
     *
     * @param arr
     * @return
     */
    public int maximumElementAfterDecrementingAndRearranging(int[] arr) {
        Arrays.sort(arr);
        arr[0] = 1;
        for (int i = 1; i < arr.length; i++) {
            arr[i] = Math.min(arr[i], arr[i - 1] + 1);
        }
        return arr[arr.length - 1];
    }

}
